SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Fibonacci coding</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Fibonacci coding</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1246091330">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><table class="sidebar sidebar-collapse nomobile nowraplinks hlist"><tbody><tr><td class="sidebar-pretitle">Part of a series on</td></tr><tr><th class="sidebar-title-with-pretitle"><a href="Numeral_system" title="Numeral system">Numeral systems</a></th></tr><tr><td class="sidebar-content-with-subgroup">

<div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="color: var(--color-base)"><div class="sidebar-list-title-c"><a href="Positional_notation" title="Positional notation">Place-value notation</a></div></div><div class="sidebar-list-content mw-collapsible-content"><table class="sidebar-subgroup"><tbody><tr><td class="sidebar-content hlist">

<div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="color: var(--color-base)"><div class="sidebar-list-title-c"><a href="Hindu%E2%80%93Arabic_numeral_system" title="Hindu–Arabic numeral system">Hindu–Arabic numerals</a></div></div><div class="sidebar-list-content mw-collapsible-content">

<ul><li><a href="Arabic_numerals" title="Arabic numerals">Western Arabic</a></li>

<li><a href="Eastern_Arabic_numerals" title="Eastern Arabic numerals">Eastern Arabic</a></li></ul>

<hr>

<ul><li><a href="Bengali_numerals" title="Bengali numerals">Bengali</a></li>

<li><a href="Devanagari_numerals" title="Devanagari numerals">Devanagari</a></li>

<li><a href="Gujarati_numerals" title="Gujarati numerals">Gujarati</a></li>

<li><a href="Gurmukhi_numerals" class="mw-redirect" title="Gurmukhi numerals">Gurmukhi</a></li>

<li><a href="Sinhala_numerals" title="Sinhala numerals">Sinhala</a></li>

<li><a href="Tamil_numerals" title="Tamil numerals">Tamil</a></li>

<li><a href="Malayalam_numerals" title="Malayalam numerals">Malayalam</a></li>

<li><a href="Telugu_script#Numerals" title="Telugu script">Telugu</a></li>

<li><a href="Kannada_script#Numerals" title="Kannada script">Kannada</a></li>

<li><a href="Dzongkha_numerals" title="Dzongkha numerals">Dzongkha</a></li></ul>

<hr>

<ul><li><a href="Tibetan_numerals" title="Tibetan numerals">Tibetan</a></li>

<li><a href="Balinese_numerals" title="Balinese numerals">Balinese</a></li>

<li><a href="Burmese_numerals" title="Burmese numerals">Burmese</a></li>

<li><a href="Javanese_numerals" title="Javanese numerals">Javanese</a></li>

<li><a href="Khmer_numerals" title="Khmer numerals">Khmer</a></li>

<li><a href="Mongolian_numerals" title="Mongolian numerals">Mongolian</a></li>

<li><a href="Sundanese_numerals" title="Sundanese numerals">Sundanese</a></li>

</tr><tr><td class="sidebar-content hlist">

<div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="color: var(--color-base)"><div class="sidebar-list-title-c">East Asian systems</div></div><div class="sidebar-list-content mw-collapsible-content">

<dl><dt>Contemporary</dt></dl>

<ul><li><a href="Chinese_numerals" title="Chinese numerals">Chinese</a>

<ul><li><a href="Hokkien_numerals" title="Hokkien numerals">Hokkien</a></li>

<li><a href="Suzhou_numerals" title="Suzhou numerals">Suzhou</a></li></ul></li>

<li><a href="Japanese_numerals" title="Japanese numerals">Japanese</a></li>

<li><a href="Korean_numerals" title="Korean numerals">Korean</a></li>

<li><a href="Vietnamese_numerals" title="Vietnamese numerals">Vietnamese</a></li></ul>

<hr>

<dl><dt>Historic</dt></dl>

<ul><li><a href="Counting_rods" title="Counting rods">Counting rods</a></li>

<li><a href="Tangut_numerals" title="Tangut numerals">Tangut</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content hlist">

<div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="color: var(--color-base)"><div class="sidebar-list-title-c">Other systems</div></div><div class="sidebar-list-content mw-collapsible-content">

<ul><li><a href="History_of_ancient_numeral_systems" title="History of ancient numeral systems">History</a></li></ul>

<hr>

<dl><dt><a href="Ancient_history" title="Ancient history">Ancient</a></dt></dl>

<ul><li><a href="Babylonian_cuneiform_numerals" title="Babylonian cuneiform numerals">Babylonian</a></li></ul>

<hr>

<dl><dt><a href="Post-classical_history" title="Post-classical history">Post-classical</a></dt></dl>

<ul><li><a href="Cistercian_numerals" title="Cistercian numerals">Cistercian</a></li>

<li><a href="Maya_numerals" title="Maya numerals">Mayan</a></li>

<li><a href="Muisca_numerals" title="Muisca numerals">Muisca</a></li>

<li><a href="Pentadic_numerals" title="Pentadic numerals">Pentadic</a></li>

<li><a href="Quipu" title="Quipu">Quipu</a></li>

<hr>

<dl><dt>Contemporary</dt></dl>

<ul><li><a href="Cherokee_syllabary#Numerals" title="Cherokee syllabary">Cherokee</a></li>

<li><a href="Kaktovik_numerals" title="Kaktovik numerals">Kaktovik</a> (Iñupiaq)</li></ul></div></div></td>

</tr><tr><td class="sidebar-content hlist">

<div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="color: var(--color-base)"><div class="sidebar-list-title-c">By <a href="Radix" title="Radix">radix/base</a></div></div><div class="sidebar-list-content mw-collapsible-content">

<dl><dt>Common radices/bases</dt></dl>

<hr>

<dl><dt><a href="Non-standard_positional_numeral_systems" title="Non-standard positional numeral systems">Non-standard radices/bases</a></dt></dl>

<ul><li><a href="Bijective_numeration" title="Bijective numeration">Bijective</a><span class="nowrap"> </span>(<a href="Unary_numeral_system" title="Unary numeral system">1</a>)</li>

<li><a href="Signed-digit_representation" title="Signed-digit representation">Signed-digit</a><span class="nowrap"> </span>(<a href="Balanced_ternary" title="Balanced ternary">balanced ternary</a>)</li>

<li><a href="Mixed_radix" title="Mixed radix">Mixed</a><span class="nowrap"> </span>(<a href="Factorial_number_system" title="Factorial number system">factorial</a>)</li>

<li><a href="Negative_base" title="Negative base">Negative</a></li>

<li><a href="Complex-base_system" title="Complex-base system">Complex</a><span class="nowrap"> </span>(<a href="Quater-imaginary_base" title="Quater-imaginary base">2<i>i</i></a>)</li>

<li><a href="Non-integer_base_of_numeration" title="Non-integer base of numeration">Non-integer</a><span class="nowrap"> </span>(<a href="Golden_ratio_base" title="Golden ratio base">φ</a>)</li>

<li><a href="Asymmetric_numeral_systems" title="Asymmetric numeral systems">Asymmetric</a></li></ul></div></div></td>

</tr></tbody></table></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="color: var(--color-base)"><div class="sidebar-list-title-c"><a href="Sign-value_notation" title="Sign-value notation">Sign-value notation</a></div></div><div class="sidebar-list-content mw-collapsible-content">

<dl><dt>Non-alphabetic</dt></dl>

<ul><li><a href="Aegean_numerals" title="Aegean numerals">Aegean</a></li>

<li><a href="Attic_numerals" title="Attic numerals">Attic</a></li>

<li><a href="Aztec_script#Numerals" title="Aztec script">Aztec</a></li>

<li><a href="Brahmi_numerals" title="Brahmi numerals">Brahmi</a></li>

<li><a href="Chuvash_numerals" title="Chuvash numerals">Chuvash</a></li>

<li><a href="Egyptian_numerals" title="Egyptian numerals">Egyptian</a></li>

<li><a href="Etruscan_numerals" title="Etruscan numerals">Etruscan</a></li>

<li><a href="Kharosthi_numerals" class="mw-redirect" title="Kharosthi numerals">Kharosthi</a></li>

<li><a href="Prehistoric_counting" class="mw-redirect" title="Prehistoric counting">Prehistoric counting</a></li>

<li><a href="Proto-cuneiform" title="Proto-cuneiform">Proto-cuneiform</a></li>

<li><a href="Roman_numerals" title="Roman numerals">Roman</a></li>

<li><a href="Tally_marks" title="Tally marks">Tally marks</a></li></ul>

<hr>

<dl><dt><a href="Alphabetic_numeral_system" title="Alphabetic numeral system">Alphabetic</a></dt></dl>

<ul><li><a href="Abjad_numerals" title="Abjad numerals">Abjad</a></li>

<li><a href="Armenian_numerals" title="Armenian numerals">Armenian</a></li>

<li><a href="Alphasyllabic_numeral_system" title="Alphasyllabic numeral system">Alphasyllabic</a>

<ul><li><a href="Aksharapalli" title="Aksharapalli">Akṣarapallī</a></li>

<li><a href="%C4%80ryabha%E1%B9%ADa_numeration" title="Āryabhaṭa numeration">Āryabhaṭa</a></li>

<li><a href="Katapayadi_system" title="Katapayadi system">Kaṭapayādi</a></li></ul></li>

<li><a href="Coptic_numerals" class="mw-redirect" title="Coptic numerals">Coptic</a></li>

<li><a href="Cyrillic_numerals" title="Cyrillic numerals">Cyrillic</a></li>

<li><a href="Ge%CA%BDez_script#Numerals" title="Geʽez script">Geʽez</a></li>

<li><a href="Georgian_numerals" title="Georgian numerals">Georgian</a></li>

<li><a href="Glagolitic_numerals" title="Glagolitic numerals">Glagolitic</a></li>

<li><a href="Greek_numerals" title="Greek numerals">Greek</a></li>

<li><a href="Hebrew_numerals" title="Hebrew numerals">Hebrew</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-below" style="border-top:1px solid #aaa;border-bottom:1px solid #aaa;">

<a href="List_of_numeral_systems" title="List of numeral systems">List of numeral systems</a></td></tr><tr><td class="sidebar-navbar"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></td></tr></tbody></table>

<p>In <a href="Mathematics" title="Mathematics">mathematics</a> and computing, <b>Fibonacci coding</b> is a <a href="Universal_code_(data_compression)" title="Universal code (data compression)">universal code</a><sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> which encodes positive integers into binary <a href="Code_word_(communication)" title="Code word (communication)">code words</a>. It is one example of representations of integers based on <a href="Fibonacci_number" class="mw-redirect" title="Fibonacci number">Fibonacci numbers</a>. Each code word ends with "11" and contains no other instances of "11" before the end.

</p><p>The Fibonacci code is closely related to the <a href="Zeckendorf_representation" class="mw-redirect" title="Zeckendorf representation">Zeckendorf representation</a>, a positional <a href="Numeral_system" title="Numeral system">numeral system</a> that uses <a href="Zeckendorf's_theorem" title="Zeckendorf's theorem">Zeckendorf's theorem</a> and has the property that no number has a representation with consecutive 1s. The Fibonacci code word for a particular integer is exactly the integer's Zeckendorf representation with the order of its digits reversed and an additional "1" appended to the end.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<p>For a number <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\!}</annotation>

</semantics>

</math></span><img src="./b4df206628eed61b48a8c51b432eca0c6520179e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-right: -0.387ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N\!}" loading="lazy"></span>, if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d(0),d(1),\ldots ,d(k-1),d(k)\!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d(0),d(1),\ldots ,d(k-1),d(k)\!}</annotation>

</semantics>

</math></span><img src="./262078eeffcf8661bf8168002c1ff818e2d9b2f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-right: -0.166ex; width:27.876ex; height:2.843ex;" alt="{\displaystyle d(0),d(1),\ldots ,d(k-1),d(k)\!}" loading="lazy"></span> represent the digits of the code word representing <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\!}</annotation>

</semantics>

</math></span><img src="./b4df206628eed61b48a8c51b432eca0c6520179e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-right: -0.387ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N\!}" loading="lazy"></span> then we have:

</p>

</mrow>

</mrow>

</munderover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=\sum _{i=0}^{k-1}d(i)F(i+2),{\text{ and }}d(k-1)=d(k)=1.\!}</annotation>

</semantics>

</math></span><img src="./53b83695d56b770fb163ba478fa2f9d9aa2c6a52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; margin-right: -0.204ex; width:47.328ex; height:7.343ex;" alt="{\displaystyle N=\sum _{i=0}^{k-1}d(i)F(i+2),{\text{ and }}d(k-1)=d(k)=1.\!}" loading="lazy"></span></dd></dl>

<p>where <span class="texhtml"><i>F</i>(<i>i</i>)</span> is the <span class="texhtml"><i>i</i></span>th <a href="Fibonacci_number" class="mw-redirect" title="Fibonacci number">Fibonacci number</a>, and so <span class="texhtml"><i>F</i>(<i>i</i>+2)</span> is the <span class="texhtml"><i>i</i></span>th distinct Fibonacci number starting with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1,2,3,5,8,13,\ldots }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1,2,3,5,8,13,\ldots }</annotation>

</semantics>

</math></span><img src="./a65971693987807896a13cbf12a1398b8c0a02d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.064ex; height:2.509ex;" alt="{\displaystyle 1,2,3,5,8,13,\ldots }" loading="lazy"></span>. The last bit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d(k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d(k)}</annotation>

</semantics>

</math></span><img src="./b59ae56ed5fb312c7303526a49d562e31ea20909.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.236ex; height:2.843ex;" alt="{\displaystyle d(k)}" loading="lazy"></span> is always an appended bit of 1 and does not carry place value.

</p><p>It can be shown that such a coding is unique, and the only occurrence of "11" in any code word is at the end (that is, <i>d</i>(<i>k</i>−1) and <i>d</i>(<i>k</i>)). The penultimate bit is the most significant bit and the first bit is the least significant bit. Also, leading zeros cannot be omitted as they can be in, for example, decimal numbers.

</p><p>The first few Fibonacci codes are shown below, and also their so-called <a href="Universal_code_(data_compression)#Relationship_to_practical_compression" title="Universal code (data compression)"><i>implied probability</i></a>, the value for each number that has a minimum-size code in Fibonacci coding.

</p>

<th>Symbol</th>

<th>Fibonacci representation</th>

<th>Fibonacci code word</th>

<th>Implied probability

</th></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(2)}</annotation>

</semantics>

</math></span><img src="./96ed3f1c8861a0fd967b693342b1692c01ea25c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.713ex; height:2.843ex;" alt="{\displaystyle F(2)}" loading="lazy"></span></td>

<td>1/4

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(3)}</annotation>

</semantics>

</math></span><img src="./9f41ad9360c4645b946b1c9915aaf6f0e35eed65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.713ex; height:2.843ex;" alt="{\displaystyle F(3)}" loading="lazy"></span></td>

<td>1/8

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(4)}</annotation>

</semantics>

</math></span><img src="./6072d779036bf7be20a086c085530915be02ccf5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.713ex; height:2.843ex;" alt="{\displaystyle F(4)}" loading="lazy"></span></td>

<td>1/16

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(2)+F(4)}</annotation>

</semantics>

</math></span><img src="./a4412431306d06aaa6c04fb46a1ca4140a5c3221.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.265ex; height:2.843ex;" alt="{\displaystyle F(2)+F(4)}" loading="lazy"></span></td>

<td>1/16

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(5)}</annotation>

</semantics>

</math></span><img src="./aa1d5dff0c4bffae5648b2c75b28599ac5956c35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.713ex; height:2.843ex;" alt="{\displaystyle F(5)}" loading="lazy"></span></td>

<td>1/32

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(2)+F(5)}</annotation>

</semantics>

</math></span><img src="./e934370caaff4714ca611c7a325677d9457c4251.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.265ex; height:2.843ex;" alt="{\displaystyle F(2)+F(5)}" loading="lazy"></span></td>

<td>1/32

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(3)+F(5)}</annotation>

</semantics>

</math></span><img src="./0df76cdbd737392b71a620751996c8aa036a6b34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.265ex; height:2.843ex;" alt="{\displaystyle F(3)+F(5)}" loading="lazy"></span></td>

<td>1/32

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(6)}</annotation>

</semantics>

</math></span><img src="./983c1d8e6d1d9c192089bdfc38b252082c45413f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.713ex; height:2.843ex;" alt="{\displaystyle F(6)}" loading="lazy"></span></td>

<td>1/64

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(2)+F(6)}</annotation>

</semantics>

</math></span><img src="./8e8c616d0596bee0b623fb517e3520f58b39f3bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.265ex; height:2.843ex;" alt="{\displaystyle F(2)+F(6)}" loading="lazy"></span></td>

<td>1/64

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(3)+F(6)}</annotation>

</semantics>

</math></span><img src="./df2d4bb9ae6e432e432b1d08c2b5ac072d4c3009.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.265ex; height:2.843ex;" alt="{\displaystyle F(3)+F(6)}" loading="lazy"></span></td>

<td>1/64

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(4)+F(6)}</annotation>

</semantics>

</math></span><img src="./4df6067228dd0211dd7a8669fbd2b2c03998c7a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.265ex; height:2.843ex;" alt="{\displaystyle F(4)+F(6)}" loading="lazy"></span></td>

<td>1/64

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(2)+F(4)+F(6)}</annotation>

</semantics>

</math></span><img src="./5912de446a9f25cbfe4d6e106eb4ab95d1987290.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.818ex; height:2.843ex;" alt="{\displaystyle F(2)+F(4)+F(6)}" loading="lazy"></span></td>

<td>1/64

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(7)}</annotation>

</semantics>

</math></span><img src="./21f23316637ae7b32258efcc5e6f305938df973f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.713ex; height:2.843ex;" alt="{\displaystyle F(7)}" loading="lazy"></span></td>

<td>1/128

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(2)+F(7)}</annotation>

</semantics>

</math></span><img src="./8402b6e67fdd68c639b259ce405114665eda6642.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.265ex; height:2.843ex;" alt="{\displaystyle F(2)+F(7)}" loading="lazy"></span></td>

<td>1/128

</td></tr>

</tbody></table>

<p>To encode an integer <span class="texhtml mvar" style="font-style:italic;">N</span>:

</p>

<ol><li>Find the largest <a href="Fibonacci_number" class="mw-redirect" title="Fibonacci number">Fibonacci number</a> equal to or less than <i><span class="texhtml mvar" style="font-style:italic;">N</span></i>; subtract this number from <i><span class="texhtml mvar" style="font-style:italic;">N</span></i>, keeping track of the remainder.</li>

<li>If the number subtracted was the <span class="texhtml mvar" style="font-style:italic;">i</span>th Fibonacci number <span class="texhtml"><i>F</i>(<i>i</i>)</span>, put a 1 in place <span class="texhtml"><i>i</i> − 2</span> in the code word (counting the left most digit as place 0).</li>

<li>Repeat the previous steps, substituting the remainder for <i><span class="texhtml mvar" style="font-style:italic;">N</span></i>, until a remainder of 0 is reached.</li>

<li>Place an additional 1 after the rightmost digit in the code word.</li></ol>

<p>To decode a code word, remove the final "1", assign the remaining the values 1,2,3,5,8,13... (the <a href="Fibonacci_number" class="mw-redirect" title="Fibonacci number">Fibonacci numbers</a>) to the bits in the code word, and sum the values of the "1" bits.

</p>

<div class="mw-heading mw-heading2"><h2 id="Comparison_with_other_universal_codes">Comparison with other universal codes</h2></div>

<p>Fibonacci coding has a useful property that sometimes makes it attractive in comparison to other universal codes: it is an example of a <a href="Self-synchronizing_code" title="Self-synchronizing code">self-synchronizing code</a>, making it easier to recover data from a damaged stream. With most other universal codes, if a single <a href="Bit" title="Bit">bit</a> is altered, then none of the data that comes after it will be correctly read. With Fibonacci coding, on the other hand, a changed bit may cause one token to be read as two, or cause two tokens to be read incorrectly as one, but reading a "0" from the stream will stop the errors from propagating further. Since the only stream that has no "0" in it is a stream of "11" tokens, the total <a href="Edit_distance" title="Edit distance">edit distance</a> between a stream damaged by a single bit error and the original stream is at most three.

</p><p>This approach, encoding using sequence of symbols, in which some patterns (like "11") are forbidden, can be freely generalized.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

<p>The following table shows that the number 65 is represented in Fibonacci coding as 0100100011, since <span class="nowrap">65 = 2 + 8 + 55</span>. The first two Fibonacci numbers (0 and 1) are not used, and an additional 1 is always appended.

</p>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

<mtext>additional</mtext>

</mrow>

</mstyle>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</menclose>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{ccccccccccc|c}\hline 0&1&1&2&3&5&8&13&21&34&55&-\\\hline F(0)&F(1)&F(2)&F(3)&F(4)&F(5)&F(6)&F(7)&F(8)&F(9)&F(10)&\scriptstyle {\text{additional}}\\\hline -&-&0&1&0&0&1&0&0&0&1&1\\\hline \end{array}}}</annotation>

</semantics>

</math></span><img src="./e39fad4dcdf757d0df2d0cbdf1e71f4082dcb992.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.838ex; width:87.951ex; height:10.843ex;" alt="{\displaystyle {\begin{array}{ccccccccccc|c}\hline 0&1&1&2&3&5&8&13&21&34&55&-\\\hline F(0)&F(1)&F(2)&F(3)&F(4)&F(5)&F(6)&F(7)&F(8)&F(9)&F(10)&\scriptstyle {\text{additional}}\\\hline -&-&0&1&0&0&1&0&0&0&1&1\\\hline \end{array}}}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Generalizations">Generalizations</h2></div>

<p>The Fibonacci encodings for the positive integers are binary strings that end with "11" and contain no other instances of "11". This can be generalized to binary strings that end with <i>N</i> consecutive 1s and contain no other instances of <i>N</i> consecutive 1s. For instance, for <i>N</i> = 3 the positive integers are encoded as 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111, …. In this case, the number of encodings as a function of string length is given by the sequence of <a href="Tribonacci_number" class="mw-redirect" title="Tribonacci number">tribonacci numbers</a>.

</p><p>For general constraints defining which symbols are allowed after a given symbol, the maximal information rate can be obtained by first finding the optimal transition probabilities using a <a href="Maximal_entropy_random_walk" title="Maximal entropy random walk">maximal entropy random walk</a>, then using an <a href="Entropy_coder" class="mw-redirect" title="Entropy coder">entropy coder</a> (with switched encoder and decoder) to encode a message as a sequence of symbols fulfilling the found optimal transition probabilities.

</p>

<ul><li><a href="Golden_ratio_base" title="Golden ratio base">Golden ratio base</a></li>

<li><a href="NegaFibonacci_coding" class="mw-redirect" title="NegaFibonacci coding">NegaFibonacci coding</a></li>

<li><a href="Ostrowski_numeration" title="Ostrowski numeration">Ostrowski numeration</a></li>

<li><a href="Universal_code_(data_compression)" title="Universal code (data compression)">Universal code</a></li>

<li><a href="Varicode" title="Varicode">Varicode</a>, a practical application</li>

<li><a href="Zeckendorf's_theorem" title="Zeckendorf's theorem">Zeckendorf's theorem</a></li>

<li><a href="Maximal_entropy_random_walk" title="Maximal entropy random walk">Maximal entropy random walk</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBasuPrasad2010" class="citation journal cs1">Basu, Manjusri; Prasad, Bandhu (2010-09-01). <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/pii/S0022314X10000533">"Long range variations on the Fibonacci universal code"</a>. <i>Journal of Number Theory</i>. <b>130</b> (9): <span class="nowrap">1925–</span>1931. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jnt.2010.01.013">10.1016/j.jnt.2010.01.013</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0022-314X">0022-314X</a>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFDuda2007" class="citation arxiv cs1">Duda, Jarek (2007). "Optimal encoding on discrete lattice with translational invariant constrains using statistical algorithms". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/0710.3861">0710.3861</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.IT">cs.IT</a>].</cite></span>

</li>

</ol></div></div>

<ul><li><cite id="CITEREFAlloucheShallit2003" class="citation book cs1">Allouche, Jean-Paul; <a href="Jeffrey_Shallit" title="Jeffrey Shallit">Shallit, Jeffrey</a> (2003). <span class="id-lock-limited" title="Free access subject to limited trial, subscription normally required"><a rel="nofollow" class="external text" href="https://archive.org/details/automaticsequenc00jpal"><i>Automatic Sequences: Theory, Applications, Generalizations</i></a></span>. <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. p. <a rel="nofollow" class="external text" href="https://archive.org/details/automaticsequenc00jpal/page/n122">105</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-82332-6</bdi>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1086.11015">1086.11015</a>.</cite></li>

<li><cite id="CITEREFFraenkelKlein1996" class="citation journal cs1">Fraenkel, Aviezri S.; Klein, Shmuel T. (1996). "Robust universal complete codes for transmission and compression". <i>Discrete Applied Mathematics</i>. <b>64</b> (1): <span class="nowrap">31–</span>55. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.3064">10.1.1.37.3064</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0166-218X%2893%2900116-H">10.1016/0166-218X(93)00116-H</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0166-218X">0166-218X</a>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0874.94026">0874.94026</a>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFStakhov2009" class="citation book cs1">Stakhov, A. P. (2009). <i>The Mathematics of Harmony: From Euclid to Contemporary Mathematics and Computer Science</i>. Singapore: <a href="World_Scientific_Publishing" class="mw-redirect" title="World Scientific Publishing">World Scientific Publishing</a>.</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Data_compression_methods241" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Data_compression_methods241" style="font-size:114%;margin:0 4em"><a href="Data_compression" title="Data compression">Data compression</a> methods</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Lossless_compression" title="Lossless compression">Lossless</a><br>type</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Entropy_coding" title="Entropy coding">Entropy</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Adaptive_coding" title="Adaptive coding">Adaptive coding</a></li>

<li><a href="Arithmetic_coding" title="Arithmetic coding">Arithmetic</a></li>

<li><a href="Asymmetric_numeral_systems" title="Asymmetric numeral systems">Asymmetric numeral systems</a></li>

<li><a href="Golomb_coding" title="Golomb coding">Golomb</a></li>

<li><a href="Huffman_coding" title="Huffman coding">Huffman</a>

<ul><li><a href="Adaptive_Huffman_coding" title="Adaptive Huffman coding">Adaptive</a></li>

<li><a href="Canonical_Huffman_code" title="Canonical Huffman code">Canonical</a></li>

<li><a href="Modified_Huffman_coding" title="Modified Huffman coding">Modified</a></li></ul></li>

<li><a href="Range_coding" title="Range coding">Range</a></li>

<li><a href="Shannon_coding" title="Shannon coding">Shannon</a></li>

<li><a href="Shannon%E2%80%93Fano_coding" title="Shannon–Fano coding">Shannon–Fano</a></li>

<li><a href="Shannon%E2%80%93Fano%E2%80%93Elias_coding" title="Shannon–Fano–Elias coding">Shannon–Fano–Elias</a></li>

<li><a href="Tunstall_coding" title="Tunstall coding">Tunstall</a></li>

<li><a href="Unary_coding" title="Unary coding">Unary</a></li>

<li><a href="Universal_code_(data_compression)" title="Universal code (data compression)">Universal</a>

<ul><li><a href="Exponential-Golomb_coding" title="Exponential-Golomb coding">Exp-Golomb</a></li>

<li><a href="Elias_gamma_coding" title="Elias gamma coding">Gamma</a></li>

<li><a href="Levenshtein_coding" title="Levenshtein coding">Levenshtein</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Dictionary_coder" title="Dictionary coder">Dictionary</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Byte-pair_encoding" title="Byte-pair encoding">Byte-pair encoding</a></li>

<li><a href="LZ77_and_LZ78" title="LZ77 and LZ78">Lempel–Ziv</a>

<li><a href="Snappy_(compression)" title="Snappy (compression)">Snappy</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Delta_encoding" title="Delta encoding">Delta</a>

<ul><li><a href="Incremental_encoding" title="Incremental encoding">Incremental</a></li></ul></li>

<li><a href="Grammar-based_code" title="Grammar-based code">Grammar</a>

<li><a href="Sequitur_algorithm" title="Sequitur algorithm">Sequitur</a></li></ul></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Hybrid</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>LZ77 + Huffman

<ul><li><a href="Deflate" title="Deflate">Deflate</a></li>

<li>LZ77 + ANS

<ul><li><a href="LZFSE" title="LZFSE">LZFSE</a></li></ul></li>

<li>LZ77 + Huffman + ANS

<ul><li><a href="Zstd" title="Zstd">Zstandard</a></li></ul></li>

<li>LZ77 + Huffman + context

<ul><li><a href="Brotli" title="Brotli">Brotli</a></li></ul></li>

<li>LZSS + Huffman

<li>LZ77 + Range

<li>LZHAM</li></ul></li>

<li>RLE + BWT + MTF + Huffman

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Lossy_compression" title="Lossy compression">Lossy</a><br>type</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Transform_coding" title="Transform coding">Transform</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Discrete_cosine_transform" title="Discrete cosine transform">Discrete cosine transform</a>

<li><a href="Wavelet_transform" title="Wavelet transform">Wavelet</a>

<ul><li><a href="Daubechies_wavelet" title="Daubechies wavelet">Daubechies</a></li>

<li><a href="Set_partitioning_in_hierarchical_trees" title="Set partitioning in hierarchical trees">SPIHT</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Predictive</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Adaptive_differential_pulse-code_modulation" title="Adaptive differential pulse-code modulation">ADPCM</a></li></ul></li>

<ul><li><a href="Algebraic_code-excited_linear_prediction" title="Algebraic code-excited linear prediction">ACELP</a></li>

<li>Motion

<ul><li><a href="Motion_compensation" title="Motion compensation">Compensation</a></li>

<li><a href="Motion_estimation" title="Motion estimation">Estimation</a></li>

<li><a href="Motion_vector" class="mw-redirect" title="Motion vector">Vector</a></li></ul></li>

<li><a href="Psychoacoustics" title="Psychoacoustics">Psychoacoustic</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Data_compression#Audio" title="Data compression">Audio</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Companding" title="Companding">Companding</a></li>

<li><a href="Convolution" title="Convolution">Convolution</a></li>

<li><a href="Dynamic_range" title="Dynamic range">Dynamic range</a></li>

<li><a href="Latency_(audio)" title="Latency (audio)">Latency</a></li>

<li><a href="Nyquist%E2%80%93Shannon_sampling_theorem" title="Nyquist–Shannon sampling theorem">Nyquist–Shannon theorem</a></li>

<li><a href="Sampling_(signal_processing)" title="Sampling (signal processing)">Sampling</a></li>

<li><a href="Silence_compression" title="Silence compression">Silence compression</a></li>

<li><a href="Sound_quality" title="Sound quality">Sound quality</a></li>

<li><a href="Speech_coding" title="Speech coding">Speech coding</a></li>

<li><a href="Sub-band_coding" title="Sub-band coding">Sub-band coding</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Audio_codec" title="Audio codec">Codec</a><br>parts</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Adaptive_differential_pulse-code_modulation" title="Adaptive differential pulse-code modulation">ADPCM</a></li>

<ul><li><a href="Algebraic_code-excited_linear_prediction" title="Algebraic code-excited linear prediction">ACELP</a></li>

<li><a href="Psychoacoustics" title="Psychoacoustics">Psychoacoustic model</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Image_compression" title="Image compression">Image</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Chroma_subsampling" title="Chroma subsampling">Chroma subsampling</a></li>

<li><a href="Coding_tree_unit" title="Coding tree unit">Coding tree unit</a></li>

<li><a href="Color_space" title="Color space">Color space</a></li>

<li><a href="Compression_artifact" title="Compression artifact">Compression artifact</a></li>

<li><a href="Image_resolution" title="Image resolution">Image resolution</a></li>

<li><a href="Macroblock" title="Macroblock">Macroblock</a></li>

<li><a href="Pixel" title="Pixel">Pixel</a></li>

<li><a href="Quantization_(image_processing)" title="Quantization (image processing)">Quantization</a></li>

<li><a href="Standard_test_image" title="Standard test image">Standard test image</a></li>

<li><a href="Texture_compression" title="Texture compression">Texture compression</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Methods</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Chain_code" title="Chain code">Chain code</a></li>

<li><a href="Deflate" title="Deflate">Deflate</a></li>

<li><a href="Fractal_compression" title="Fractal compression">Fractal</a></li>

<li><a href="Wavelet_transform" title="Wavelet transform">Wavelet</a>

<ul><li><a href="Daubechies_wavelet" title="Daubechies wavelet">Daubechies</a></li>

<li><a href="Set_partitioning_in_hierarchical_trees" title="Set partitioning in hierarchical trees">SPIHT</a></li></ul></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Data_compression#Video" title="Data compression">Video</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Display_resolution" title="Display resolution">Display resolution</a></li>

<li><a href="Film_frame" title="Film frame">Frame</a></li>

<li><a href="Frame_rate" title="Frame rate">Frame rate</a></li>

<li><a href="Video_compression_picture_types" title="Video compression picture types">Frame types</a></li>

<li><a href="Interlaced_video" title="Interlaced video">Interlace</a></li>

<li><a href="Video#Characteristics_of_video_streams" title="Video">Video characteristics</a></li>

<li><a href="Video_quality" title="Video quality">Video quality</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Video_codec" title="Video codec">Codec</a><br>parts</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Deblocking_filter" title="Deblocking filter">Deblocking filter</a></li>

<li><a href="Lapped_transform" title="Lapped transform">Lapped transform</a></li>

<li>Motion

<ul><li><a href="Motion_compensation" title="Motion compensation">Compensation</a></li>

<li><a href="Motion_estimation" title="Motion estimation">Estimation</a></li>

<li><a href="Motion_vector" class="mw-redirect" title="Motion vector">Vector</a></li></ul></li>

<li><a href="Wavelet_transform" title="Wavelet transform">Wavelet</a>

<ul><li><a href="Daubechies_wavelet" title="Daubechies wavelet">Daubechies</a></li>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Information_theory" title="Information theory">Theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Compressed_data_structure" title="Compressed data structure">Compressed data structures</a>

<ul><li><a href="Compressed_suffix_array" title="Compressed suffix array">Compressed suffix array</a></li>

<li><a href="FM-index" title="FM-index">FM-index</a></li></ul></li>

<li><a href="Entropy_(information_theory)" title="Entropy (information theory)">Entropy</a></li>

<li><a href="Information_theory" title="Information theory">Information theory</a>

<ul><li><a href="Timeline_of_information_theory" title="Timeline of information theory">Timeline</a></li></ul></li>

<li><a href="Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a></li>

<li><a href="Prefix_code" title="Prefix code">Prefix code</a></li>

<li><a href="Quantization_(signal_processing)" title="Quantization (signal processing)">Quantization</a></li>

<li><a href="Rate%E2%80%93distortion_theory" title="Rate–distortion theory">Rate–distortion</a></li>

<li><a href="Redundancy_(information_theory)" title="Redundancy (information theory)">Redundancy</a></li>

<li><a href="Data_compression_symmetry" title="Data compression symmetry">Symmetry</a></li>

<li><a href="Smallest_grammar_problem" title="Smallest grammar problem">Smallest grammar problem</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Community</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Hutter_Prize" title="Hutter Prize">Hutter Prize</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">People</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Mark_Adler" title="Mark Adler">Mark Adler</a></li>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-21" href="https://en.wikipedia.org/wiki/?title=Fibonacci_coding&oldid=1296653206">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>